
import numpy as np
import matplotlib.pyplot as plt

def genetic_algorithm(f, r, esp):
    n = np.ceil((r[1]-r[0])/esp)
    nbitlen = int(np.ceil(np.log(n)/np.log(2)))

    coding = lambda x: r[0] + x * (r[1]-r[0]) / n
    fitness = lambda x: f(coding(x))

    (popsize, crosize, mutsize) = (100, 50, 50)   # 每次迭代的种群数目、交叉数目和变异数目

    xs = np.zeros(popsize + crosize + mutsize, 'int')
    xs[0:popsize] = np.linspace(0, n, popsize).astype('int')
    
    fits = np.zeros(popsize + crosize + mutsize)

    result = (xs[0], fitness(xs[0]))

    count = 0

    while True:
        # 复制

        index = popsize
        # 交叉
        while index < popsize + crosize:

            cs = np.random.randint(0, popsize, 2)
            
            x0bin = bin(xs[cs[0]]).replace('0b', '').rjust(nbitlen, '0')
            x1bin = bin(xs[cs[1]]).replace('0b', '').rjust(nbitlen, '0')

            b = np.random.randint(1, nbitlen)
            
            x0_new = int(x0bin[0:b]+x1bin[b:nbitlen], 2)
            x1_new = int(x1bin[0:b]+x0bin[b:nbitlen], 2)

            if x0_new not in xs[0:index] and x0_new < n:
                xs[index] = x0_new
                index += 1

            if x1_new not in xs[0:index] and x1_new < n and index < popsize + crosize:
                xs[index] = x1_new
                index += 1


        # 变异
        while index < popsize + crosize + mutsize:
            i = np.random.randint(0, popsize)
            xbin = list(bin(xs[i]).replace('0b', '').rjust(nbitlen, '0'))

            b = np.random.randint(0, nbitlen)
            xbin[b] = '0' if xbin[b] == '1' else '0'

            xnew = int(''.join(xbin), 2)

            if xnew not in xs[0:index] and xnew < n:
                xs[index] = xnew
                index += 1
        
        # 排序
        fits = fitness(xs)
        s = np.argsort(-fits)
        xs = xs[s]
        fits = fits[s]
        
        # 检查终止条件
        if result[1] == xs[0] or result[0] == fits[0]:
            count += 1
            if count > 3:
                break
        else:
            count = 0

        result = (fits[0], xs[0])

    return (fits[0], coding(xs[0]))

def show_function(f, r, esp):
    
    x = np.linspace(r[0], r[1],1000)
    y = f(x)
    plt.plot(x, y)

    (yb,xb) = genetic_algorithm(f, r, esp)

    plt.plot(xb, yb, 'o')
    plt.show()



if __name__ == '__main__':
    f = lambda x: x*np.sin(x*2+1)**2 + 1
    r = [-3, 30]
    esp = 0.00001
    n = np.ceil((r[1]-r[0])/esp)
    #show_function(f, r, 0.00001)

    import time
    s = time.time()
    xs = np.linspace(r[0], r[1], n)
    ys = f(xs)
    i = np.argsort(-ys)
    (x, y) = (xs[i[0]], ys[i[0]])
    print(time.time() - s)
    print((x,y))

    s = time.time()
    (y, x) = genetic_algorithm(f, r, esp)
    
    print(time.time() - s)
    print((x,y))
